package Niuke;

import sun.tools.jconsole.inspector.XNodeInfo;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;


//lru
public class Solution{
    class Node{
        int key;
        int val;
        Node pre;
        Node next;

        public Node(int key,int val){
            this.key=key;
            this.val=val;
        }
    }
    class MultipleDirecList{
        Node head;
        Node tail;

        public MultipleDirecList(){

        }
    }

    //key -node
    HashMap<Integer,Node> data=new HashMap<>();
    MultipleDirecList list=new MultipleDirecList();
    int capacity;
    int cursize;

    public Solution(int capacity) {
        // write code here
        this.capacity=capacity;
    }

    public int get(int key) {
        // write code here
        if (data.containsKey(key)){
            transfer(data.get(key));
            return data.get(key).val;
        }else
            return -1;
    }

    public void set(int key, int value) {
        // write code here
        if (cursize==0){
            Node head=new Node(key,value);
            data.put(key,head);
            head.next=null;
            head.pre=null;
            list.head=head;
            list.tail=head;
            cursize++;
        }else if (data.containsKey(key)){
            data.get(key).val=value;
            transfer(data.get(key));
        }else {
            if (cursize==capacity){
                data.remove(list.head.key);
                Node head2= list.head.next;
                list.head.next=null;
                head2.pre=null;
                list.head=head2;
                Node newNode=new Node(key,value);
                newNode.next=null;
                data.put(key,newNode);
                list.tail.next=newNode;
                newNode.pre= list.tail;
                list.tail=newNode;
            }else {
                Node newNode=new Node(key,value);
                newNode.next=null;
                data.put(key,newNode);
                list.tail.next=newNode;
                newNode.pre= list.tail;
                list.tail=newNode;
                cursize++;
            }
        }
    }
    public void transfer(Node node){
        if (node.next==null)
            return;
        if (node.pre==null){
            Node head2=node.next;
            node.next.pre=null;
            node.next=null;
            list.tail.next=node;
            node.pre= list.tail;
            list.tail=node;
            list.head=head2;
            return;
        }
        node.pre.next=node.next;
        node.next.pre=node.pre;
        node.pre=null;
        node.next=null;
        list.tail.next=node;
        node.pre= list.tail;
        list.tail=node;
    }

    public static void main(String[] args) {
        Solution solution = new Solution(2);
        solution.set(1,1);
        solution.set(2,2);
        System.out.println(solution.get(1));
        solution.set(3,3);
        System.out.println(solution.get(2));
        solution.set(4,4);
        System.out.println(solution.get(1));
    }
}
